package offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/17
 **/
public class FourSum {
    public static void main(String[] args) {
        final int[] TEST01 = new int[]{1,0,-1,0,-2,2};
        final int[] TEST02 = new int[]{2,2,2,2,2};
        fourSum(TEST02,8);
    }


    /*
        先排序，然后固定一个数双指针
     */
    public static List<List<Integer>> fourSum(int[] nums, int target){
        Arrays.sort(nums);
        int p1,p2,p3,p4;
        List<List<Integer>> ans = new ArrayList<>();
        boolean visited = false;
        for (p1 = 0; p1 < nums.length; p1++) {
            if( p1 > 0 && nums[p1] == nums[p1-1]){
                continue;
            }
            visited = false;
            for ( p2 = p1 + 1; p2 < nums.length-2; p2++) {
                if(visited && nums[p2] == nums[p2-1]){
                    continue;
                }
                visited = true;
                p3 = p2 + 1;
                p4 = nums.length - 1;
                while(p3 < p4){
                    if( nums[p1] + nums[p2] + nums[p3] + nums[p4] == target){
                        List<Integer> temp = new ArrayList<>();
                        ans.add(temp);
                        temp.add(nums[p1]);
                        temp.add(nums[p2]);
                        temp.add(nums[p3]);
                        temp.add(nums[p4]);
                        /*
                            去除重复
                         */
                        p3++;
                        p4--;
                        while( p3 < p4){
                            if(nums[p3] == nums[p3-1]){
                                p3++;
                            }else{
                                break;
                            }
                        }
                        while(p3 < p4){
                            if(nums[p4] == nums[p4+1]){
                                p4--;
                            }else{
                                break;
                            }
                        }
                    }else if(nums[p1] + nums[p2] + nums[p3] + nums[p4] < target){
                        p3++;
                    }else{
                        p4--;
                    }

                }
            }
        }
        return ans;
    }
}
